I. Field of the Invention
The present invention relates generally to a data transfer procedure for transferring data of a data sequence between a transmitting entity and a receiving entity. The invention also relates to a communication system and to a transmitting entity in which the procedure is effected. The invention provides a method of and apparatus for recovering data lost in a transmission, and is useful for improving the reliability of data unit delivery in a packet radio system but is not limited to such an application.
II. Description of the Related Art
The general packet radio system (GPRS) is a packet data based communication system that has been developed for GSM networks with the aim of providing networks built to this standard with a way to handle higher data speeds and packet switched connections. GPRS can also be used in time division multiple access (TDMA) networks (IS-136). It is intended to provide a transitional path to third generation (3G) wireless data services It enables the introduction of packet switching and Internet Protocol (IP). The GPRS standard is now well defined and is currently being deployed in existing GSM-based mobile networks, in order to provide a way for GSM operators to meet the growing demand for wireless packet data services.
The GPRS standard defines a logical link control (LLC) layer which provides a logical link between a mobile station (MS) and a serving GPRS support node (SGSN). The logical link control (LLC) provides services necessary to maintain a ciphered data link between the MS and the SGSN. The logical link is maintained as the MS moves between cells serviced by the same SGSN. When the MS moves to a cell being serviced by a different SGSN the existing connection is released and a new logical link connection is established.
The logical link control (LLC) provides for acknowledged and unacknowledged point-to-point delivery of LLC protocol data units (PDUs) between the mobile station (MS) and the serving GPRS support node (SGSN) and point to multipoint delivery of packets from the SGSN to the MS. The LLC layer also provides for detecting errors from corrupted PDUs by checking a frame check sequence (FCS) in the LLC frame format. The FCS contains the value of a cyclic redundancy check (CRC) calculation performed over a header and information fields in a frame. For the acknowledged mode of transfer, the LLC may request retransmission of the frames of data for which an acknowledgement has not been received.
Network layer protocols are intended to operate over services derived from a wide variety of sub-networks and data links. GPRS supports several network layer protocols providing protocol transparency for users of the service. All functions relating to the transfer of network protocol data units (N-PDUs) are carried out transparently by GPRS network entities. A layer known as the Sub-Network Dependant Convergence Protocol (SNDCP) provides this protocol transparency and support for a variety of network layer protocols. The SNDCP is logically situated below the network layer and above the LLC layer. It performs multiplexing of data coming from different sources before the data is sent via the logical link control (LLC) layer.
Data to be transmitted is first multiplexed by the SNDCP. The data is then segmented to maximum length LLC frames that are then sent over the LLC to the mobile station (or other network entity). At the receiving entity the SNDCP layer reassembles the data in the LLC frames. The SNDCP can request that the data be transmitted in an acknowledged mode or an unacknowledged mode. In the acknowledged mode, the receipt of data is confirmed as delivered by the LLC layer and data transmission and reception between the SNDCP and LLC layers is done in order. In the unacknowledged mode, the receipt of data is not confirmed.
The nature of logical link control (LLC) operation is such that for an acknowledged operation, network protocol data unit (N-PDU) delivery confirmations from a sending LLC entity to a sending sub-network dependant convergence protocol (SNDCP) entity may be given in a non-sequential manner. N-PDU deliveries by a receiving LLC entity to a receiving SNDCP entity, on the other hand, must be given sequentially. In the case where multiple N-PDU buffering is employed in the sending SNDCP entity, the currently specified SNDCP operation is flawed under certain circumstances.
These circumstances may arise when the sending SNDCP entity has received delivery confirmation for a buffered N-PDU and discarded the buffered copy but, due to a loss of an earlier N-PDU on the radio link, the receiving LLC entity has not yet been able to pass on a completed sequence to the receiving SNDCP entity. Under the GPRS standard when a radio link deteriorates below a certain level or simply is broken, the system may initiate a link reestablishment procedure. Alternatively, an MS may move to another cell served by a different SGSN, and so an inter-SGSN routing area update procedure aimed at reestablishing the link may be invoked.
As a result of these procedures, the receiving LLC entity's re-sequencing buffer will be purged. In effect, the logical link is reset before continuing with the data transfer. However, if one of these procedures should occur after the sending entity has received delivery confirmation, but before the receiving LLC entity has passed on the completed sequence to the receiving SNDCP entity, the missing N-PDU will be lost in the purge. Any subsequent retransmission recovery procedures will fail to recover the lost data.
The problem may be better understood from consideration of the accompanying FIG. 1, which shows an example of how the SNDCP and LLC layers at a mobile station (MS) and a serving GPRS node (SGSN) interact over time under one of the aforementioned circumstances. FIG. 1 is divided into two parts. FIG. 1a shows the uplink transfer of data (i.e. from a mobile station to an SGSN) under normal and deteriorating conditions, and FIG. 1b shows how an LLC link is reestablished and recovered following failure of the link.
FIG. 1a shows time lines for an SNDCP layer 11 and an LLC layer 12 for a mobile station (MS) 13, and time lines for an LLC layer 17 and an SNDCP layer 18 for a serving GPRS node (SGSN) 19. Initially, a register or other buffer or store 21 in the SNDCP layer 11 in the MS 13 has two network protocol data units (N-PDUs), shown as segments [5,0] and [5,1] for transfer to the SGSN 19. The GPRS standard refers to these segments as sub-network protocol data units (SNPDUs), but the term “segment” will be used herein for the sake of clarity. The legend [5,0] represents the 0th segment of the 5th N-PDU in a sequence of N-PDUs. At this point in time, the segment [5,0] has already been sent from the MS 13 to the SGSN 19 and the segment [5,1] is about to be sent. The segment [5,0] is held in a register (or other suitable storage medium) by the SNDCP layer until it (the SNDCP layer) gets confirmation that all segments of the NPDU have been received by the receiving entity (i.e. the SGSN 19).
The SNDCP layer 11 sends a logical link data request 20 to the LLC layer 12 and that causes the LLC layer 12 to transmit an information-and-supervisory (I+S) frame 22 to the LLC 17 at the SGSN 19. The I+S frame 22 contains an acknowledgement request (A) for the receiving SGSN 19 asking it to send back an acknowledgement when the data has been received. The I+S frame 22 also contains both information in the form of the SNPDU segment [5,1] and supervisory data, which includes the send sequence number N(s) of the I+S frame.
In the example, the send sequence number is 54. Receipt of the I+S frame 22 at the LLC 17 causes the value in a register V(R) to be set to N(S)+1. The value V(R) indicates the number N(S) of the next in sequence expected to be received. N(S)=54 has just been received so the next number expected in the sequence is N(S)=55 and therefore the value in the register V(R) is set to 55. The LLC 17 passes the segment [5,1] up to the SNDCP 18 together with an indication LL-DATA-IND 23 indicating receipt at the LLC layer of all segments in sequence of this, the 5th, N-PDU.
The receiving LLC 17 also sends a supervisory S frame 24 back down to the sending LLC 12 in the MS 13, which S frame 24 includes a receiver ready RR flag and a next in sequence field N(R) indicating the number of the next frame in the sequence expected to be received by the LLC 17, in this case field 55. The LLC 12 at the MS 13 reacts to that S frame 24 by setting a register V(A) equal to 55, i.e. the value V(A) of the next in-sequence frame number to be acknowledged as received. That, in turn, causes a confirmation of receipt LL-DATA-CNF 25 to be sent up to the SNDCP layer 11 of the MS, confirming that both segments 0 and 1 of the 5th N-PDU have been delivered. This causes the SNDCP 11 to delete the buffered copy of the 5th NPDU from its buffer 21.
The next N-PDU segment in the sequence is [6,0]. For the sake of this example, the segment is shown as being transmitted in an I+S frame 26 without a request for an acknowledgment. The N-PDU [6,0] is transferred over to the receiving SNDCP 18 of the SGSN 19 in the same manner as previously described, except that there is no acknowledgement sent back once the data has been received. A register 27 in the LLC 12 of the MS 13 holds a buffered copy of the frame N(S)=55, that records that the data has been sent but not acknowledged as received by the receiving LLC entity 17.
For the purpose of explanation, assume now that the transfer conditions deteriorate, as represented by the broken line 28 in FIG. 1a. The next N-PDU segment in the sequence [6,1] is transferred from the SNDCP layer of the MS 13 to the LLC layer 12 where it is transmitted in an I+S frame 29 together with other system data including an acknowledgement request A. An entry, N(S)=56 is added to the register 27 indicating that that data too has been sent and not yet acknowledged as received.
Normally, the receiving LLC entity 17 would in due course send back an acknowledgement of receipt of the segment [6,1], as requested. Receipt of the segment [6,0] is implicit in the receipt of an acknowledgement of the segment [6,1]. However, in this example, the segment [6,1] has not transferred to the receiving SGSN and therefore no acknowledgement is sent by the receiving LLC layer 17.
Next, the SNDCP provides N-PDU [7,0] to the LLC 12 for transmission. Buffered frame N(S)=57 is added to the register 27 for the segment [7,0] and the segment is transmitted between the LLCs 12 and 17 in an I+S frame 30. That frame 30 gets through to the receiving LLC 17. However, the receiving LLC 17 can determine from the register V(R)=56 that the next in sequence frame should be 56, and not 57, the sequence number in the frame that it has just received. It therefore determines that the 56th frame in the sequence has not yet got through.
As mentioned previously herein, one of the tasks of the LLC layer is to order the data in the correct sequence before passing it up to the SNDCP. The LLC 17 therefore holds onto segment [7,0] and does not pass it up to the SNDCP layer 18 of the SGSN 19. It does, however, send back an acknowledgement ACK in an S frame 31, together with an indicator N(R)=56. The acknowledgement is for the frame 57 (for which an acknowledgement was requested) and the indicator tells the sending LLC 12 that the receiving LLC has received all frames up to frame 55.
Implicit in this is that the segment conveyed by frame N(S)=56 is therefore lost. The sending LLC 12 responds to this implicit information by clearing the register 27 of the buffered frame copies N(S)=55 and N(S)=57, because these have been acknowledged as having been received by the SGSN 19, and by sending information LL-DATA-CNF 33 confirming delivery to the SGSN 19. First, the LLC 12 sends up a receipt of the [6,0] segment and next it sends up a delivery confirmation for the [7,0] segment. The SNDCP deduces from this that segment [6,1] has not been received and so holds onto buffered copies of both it and segment [6,0]. Together segments [6,0] and [6,1] make up the 6th N-PDU and all of the information for that N-PDU is retained by the transmitting SNDCP 11, until delivery has been confirmed.
At this point in time the LLC 12 attempts to retransmit the missing segment [6,1], as represented by broken line 30′. The SNDCP 11 provides the LLC 12 with the next segment [7,1] in the sequence for transmission to the receiving entity. The register 27 therefore contains retransmission copies of both the segment [6,1] (N(S)=56) and the segment [7,1] (N(S)=58). An I+S frame 35 is transmitted containing segment [7,1] and that frame is received by the receiving LLC.
The Receiving LLC sends back a S frame 36 to the transmitting LLC, which S frame 36 contains both a selective acknowledgement (SACK) of the two sequence numbers N(S)=57 and 58 and the indicator N(R)=56. The presence of the indicator, again, implies that frame 56 is still lost. The retransmission copy of frame of N(S)=58 is removed from the register 27 and a signal LL-DATA-CNF 38 confirming delivery of the segment [7,1] is sent up to the SNDCP 11. The segments [7,0] and [7,1] are therefore considered by the SNDCP layer 11 to have been delivered and are removed from the retransmission buffer of that layer.
The mobile station then waits for a predetermined period of time as determined by a system timer 40, known as “T201”. When the T201 timer period expires, another attempt is made (Retx#2) to transmit the I+S frame 30″ containing the segment [6,1]. That attempt also fails (as determined by a lack of a reply by the time that T201 40′ again expires) and so a further attempt is made to transmit the I+S frame. This is represented by the retransmission (Retx#3) 30′″ shown at the bottom of FIG. 1a. 
The timeline is continued at the top of FIG. 1b. When the number of failed retransmissions is equal to a value held in a register 41 known in the GPRS standard as “N200” (in this example N200=3), the LLC 12 at the MS 13 responds by abandoning the retries and attempting instead to reestablish the LLC link. The LLC 12 at the transmitting mobile station (MS) transmits an unnumbered or “U” frame 42 containing an LLC layer 2 initiated SABM command (set asynchronous balanced mode). The purpose of this is to cause the LLC link to be reset prior to the link being reestablished.
The LLC at the receiving SGSN responds by sending back to the LLC at the transmitting MS a U frame 43 containing an unnumbered acknowledgement response (UA layer 2) which is taken as an acknowledgement of the SABM command. Both LLCs 12, 17 then send a signal LL-ESTABLISH-IND to their respective SNDCP layers 11, 18 containing the information XID=None, which implies a layer 2 originated instruction, i.e. an LLC originating instruction. The registers at LLC layers in both the transmitting MS and the receiving SGSN are then flushed (contents reset to zero or other quiescent state) and the LLC link is thus reset.
The next few operations serve to recover from re-establishing the link. Note the similarity with the first few exchanges shown in FIG. 1a. First, the SNDCP 11 at the MS 13 resends down to the LLC layer 12 the data for segment [6,0] in the form of a logical link data request 44 that causes the LLC layer 12 to transmit an information-and-supervisory (I+S) frame 45 to the receiving LLC 17 at the SGSN 19.
This I+S frame 45 (N(S)=0) is received in-sequence, so the data for the N-PDU segment [6,0] is simply passed by the LLC layer 17 up to the receiving SNDCP 19. The I+S frame 45 contains supervisory data, which includes the send sequence number N(s) of the N-PDU. In the example, the send sequence number N(S) is now 0 because the LLC layers have been reset. Receipt of the I+S frame 45 at the LLC 17 causes the value in a register V(R) to be set to N(S)+1=1. The value V(R) indicates the number of the next in sequence expected to be received. The LLC layers have been reset to zero so the next number expected to be received will be 1, i.e. V(R)=1.
The segment [6,1] is next resent down from the SNDCP layer 11 of the MS 13 to the LLC layer 12. The LLC layer 12 reacts by transmitting another information-and-supervisory (I+S) frame 46 to the LLC 17 at the SGSN 19. This time the I+S frame 46 does contain an acknowledgement field A, effectively asking the receiving LLC 17 to send back an acknowledgement when the data has been received. The I+S frame 46 also contains the send sequence number N(S)=1. Receipt of the I+S frame 46 at the LLC 17 causes the value V(R) to be set to 2. The LLC 17 passes the segment [6,1] up to the SNDCP 18 as it was received in-sequence.
The LLC 17 also sends a supervisory S frame 48 back down to the LLC 12 in the MS 13 including a receiver ready RR flag and a next in sequence field N(R) indicating the number of the next frame in the sequence expected to be received by the LLC 17, in this case field 2. The LLC 12 at the MS 13 reacts to that S frame 48 by setting a register V(A) equal to 2, i.e. the value of the next in-sequence frame number to be acknowledged as received. That, in turn, causes a confirmation of delivery LL-DATA-CNF to be sent up to the SNDCP layer 11 of the MS 13, confirming that both segments 0 and 1 of the 6th N-PDU have been delivered.
The SNDCP 11 was “told” earlier that the receiving SGSN had received the 7th N-PDU. When the receiving LLC 17 received segments [7,0] and [7,1] it sent back an acknowledgement SACK=57+58 in an S frame 36 (see FIG. 1a) and the retransmission copy of NPDU 7 was deleted from register 21. The 6th N-PDU has also been received and acknowledged as such, so the SNDCP “thinks” that the next segment to be sent is [8,0] and behaves accordingly.
However, the truth is that the 7th N-PDU never got sent up to the SNDCP 18 layer of the receiving SGSN 19 because the LLC 17 thereof was waiting for the receipt of segment [6,1], so that it could pass all of the segments [6,1], [7,0] and [7,1] up to the SNDCP layer 18 in-sequence, as it is required to do. When the LLC layers 12, 17 were reset the segments [7,0] and [7,1] in LLC 17 were deleted. As the sending SNDCP 11 has already deleted its retransmission copy of NPDU 7 when earlier delivery confirmation was given by sending LLC 12, there is no way to resend NPDU 7 and so NPDU 7 is permanently lost under these procedures.
However, this is unsatisfactory because the purpose of the LLC and SNDCP layers in the acknowledged mode of operation is to provide a highly reliable link without data loss, for use by fault intolerant applications. The standard as currently defined is therefore failing in its stated task.